package pers.sloera.leetcode.editor.cn;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 最大平均通过率
 *
 * @author sloera
 * @date 2023-02-19 10:18:11
 */
class MaximumAveragePassRatio {
    public static void main(String[] args) {
        Solution solution = new MaximumAveragePassRatio().new Solution();
        // double v = solution.maxAverageRatio(new int[][]{{1, 2}, {3, 5}, {2, 2}}, 2);
        double v = solution.maxAverageRatio(new int[][]{{2, 4}, {3, 9}, {4, 5}, {2, 10}}, 4);
        System.out.println(v);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double maxAverageRatio(int[][] classes, int extraStudents) {
            // 哪个最大加哪个，排序交给优先队列自己做
            PriorityQueue<int[]> classQueue = new PriorityQueue<>((x, y) -> {
                if (x[0] == x[1]) {
                    return 1;
                }
                double xDiff = ((x[0] + 1) / (double) (x[1] + 1)) - (x[0] / (double) x[1]);
                double yDiff = ((y[0] + 1) / (double) (y[1] + 1)) - (y[0] / (double) y[1]);
                return Double.compare(yDiff, xDiff);
            });
            classQueue.addAll(Arrays.asList(classes));
            while (extraStudents > 0 && classQueue.peek() != null) {
                int[] poll = classQueue.poll();
                poll[0] += 1;
                poll[1] += 1;
                classQueue.add(poll);
                extraStudents--;
            }
            return classQueue.stream().mapToDouble(cla -> cla[0] / (double) cla[1]).average().orElse(0);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
